package com.qrpcw.algorithms;

import java.util.Random;

public class RandomSelectQuickSort {
	
	public static void main(String[] args) {
		int[] a = new int[]{16,14,10,8,7,9,3,2,4,11,5,1,6};
		RandomSelectQuickSort test = new RandomSelectQuickSort();
		int theElement = 12;
		int n = test.rSelect(a, theElement);
		System.out.println("The "+ theElement + "th smallest element is: " + n);
	}
	
	public void exchange(int[] A,int i, int j){
		int temp; temp = A[i]; A[i] = A[j]; A[j]=temp;
	}
	
	public int rSelect(int[] A, int n){ return randomizedSelect(A,0,A.length-1,n);}
	
	public int partition(int[] A,int p, int r){
		int x = A[r];
		int i = p-1;
		for(int j=p; j<r; j++){
			if (A[j] < x){
				i = i + 1;
				exchange(A,i,j);
			}
		}
		exchange(A,i+1,r);
		return i+1;
	}
	public int randomizedPartition(int[] A,int p, int r){
		int i = random(A,p,r); 
		//pick a random number location from Array A between p to r;
		exchange(A, r, i);
		return partition(A, p, r);
	}
	
	public int random(int[] A,int p, int r){
		Random rand = new Random();
		int randomNumber = p + rand.nextInt(r-p);
		return randomNumber;
	}
	
	public int randomizedSelect(int[] A, int p, int r, int i){
		if(p == r){
			return A[p];
		}
		int q = randomizedPartition(A, p, r);
		int k = q - p + 1;
		if(i == k){
			return A[q];
		}else if(i < k){
			return randomizedSelect(A, p, q-1, i);
		}else{
			return randomizedSelect(A, q+1, r, i-k);
		}
	}
}
